package com.lz.dc;

import java.util.ArrayList;
import java.util.List;

/**
 * 分治算法，递归
 */
public class Leetcode {

    public static void main(String[] args) {
        Leetcode leetcode = new Leetcode();
        List<Integer> list0 = leetcode.diffWaysToCompute("2*3-4*5");
        System.out.println(list0);
    }

    /**
     * 241. 为运算表达式设计优先级
     * <p>
     * 输入: "2*3-4*5"
     * 输出: [-34, -14, -10, -10, 10]
     * 解释:
     * (2*(3-(4*5))) = -34
     * ((2*3)-(4*5)) = -14
     * ((2*(3-4))*5) = -10
     * (2*((3-4)*5)) = -10
     * (((2*3)-4)*5) = 10
     * <p>
     * <p>
     * 题解：
     * 1.找到字符串中的运算符，将字符串S分割成A和B；
     * 2.递归求解A和B的所有可能结果，遍历求得A和B的所有结果根据运算符计算后的结果；
     * 3.递归终止条件：字符串中已经没有运算符，将字符串转换成数字输出；
     *
     * 题解:
     * 采用dp，待完成
     * https://leetcode-cn.com/problems/different-ways-to-add-parentheses/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-5/
     *
     * @return
     */
    public List<Integer> diffWaysToCompute(String input) {

        boolean flag = true;

        List<Integer> list0 = new ArrayList<>();
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);

            if (isOperation(ch)) {
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i + 1));

                switch (ch) {
                    case '+':
                        for (int l = 0; l < left.size(); l++) {
                            for (int r = 0; r < right.size(); r++) {
                                int i1 = left.get(l) + right.get(r);
                                list0.add(i1);
                            }
                        }
                        break;
                    case '-':
                        for (int l = 0; l < left.size(); l++) {
                            for (int r = 0; r < right.size(); r++) {
                                int i1 = left.get(l) - right.get(r);
                                list0.add(i1);
                            }
                        }
                        break;
                    case '*':
                        for (int l = 0; l < left.size(); l++) {
                            for (int r = 0; r < right.size(); r++) {
                                int i1 = left.get(l) * right.get(r);
                                list0.add(i1);
                            }
                        }
                        break;

                }
                flag = false;
            }
        }
        if (flag) list0.add(Integer.valueOf(input));

        return list0;
    }

    boolean isOperation(char ch) {
        return ch == '-' || ch == '*' || ch == '+';
    }
}